package main

//#link: https://leetcode-cn.com/problems/find-majority-element-lcci/
func main() {

}

//Boyer-Moore 投票算法
//每一轮投票过程中，从数组中删除两个不同的元素，直到投票过程无法继续，此时数组为空或者数组中剩下的元素都相等。
//如果数组为空，则数组中不存在主要元素；
//如果数组中剩下的元素都相等，则数组中剩下的元素可能为主要元素。
//维护一个候选主要元素 candidate 和候选主要元素的出现次数 count，初始时 candidate 为任意值，count=0；
//遍历数组 nums 中的所有元素，遍历到元素 xx 时，进行如下操作：
//如果count=0，则将 x 的值赋给 candidate，否则不更新 candidate 的值；
//如果candidate，则将 count 加 1，否则将count 减 1。
//遍历结束之后，如果数组 nums 中存在主要元素，则 candidate 即为主要元素，否则 candidate 可能为数组中的任意一个元素。
//由于不一定存在主要元素，因此需要第二次遍历数组，验证candidate 是否为主要元素。第二次遍历时，统计candidate 在数组中的出现次数，如果出现次数大于数组长度的一半，则candidate 是主要元素，返回 candidate，否则数组中不存在主要元素，返回 -1−1。
func majorityElement(nums []int) int {
	candidate, count := -1, 0
	for _, num := range nums {
		if count == 0 {
			candidate = num
		}
		if candidate == num {
			count++
		} else {
			count--
		}
	}
	count = 0
	for _, num := range nums {
		if num == candidate {
			count++
		}
	}
	if count > len(nums)>>1 {
		return candidate
	}
	return -1
}
